package 单周赛.september;

import java.util.Arrays;
import java.util.List;

/**
 * @
 * @date 2024/09/08
 */
public class 第414场单周赛 {

    public static void main(String[] args) {

    }

    public String convertDateToBinary(String date) {
        String y = date.substring(0, 4);
        String m = date.substring(5, 7);
        String d = date.substring(8);


        return Integer.toBinaryString(Integer.valueOf(y)) + "-" +
                Integer.toBinaryString(Integer.valueOf(m)) + "-" +
                Integer.toBinaryString(Integer.valueOf(d));
    }

    /**
     * 二分答案+排序
     * 得分越小，越容易满足答案
     * 1，最大可能得分的最大值为数组中 最大值-最小值+d
     * 2，假设最大得分 score ， 判断数组是否可以满足两两之间最小绝对值
     * 每个数之间的差是 >= score 的
     * 假设数组为  [a,b,c]
     * 那么第一个数取  a
     * 第二个数从 [b,b+d] 中选择
     * 如果 a+score > b+d ，那么不满足条件
     * 否则取 max(a+score,b) b 可能比 a+score 大，想要使得 c 尽可能和 b的差大，
     * 那么 b 这个区间尽可能选小的 b，而不是 (b,b+d] 中的数
     */
    public int maxPossibleScore(int[] start, int d) {
        int ans = 0;
        Arrays.sort(start);

        int left = 0, right = start[start.length - 1] - start[0] + d;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (valid(start, mid, d)) {
                ans = Math.max(ans, mid);
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return ans;
    }

    private boolean valid(int[] start, int maxScore, int d) {
        // 注意数字溢出
        long curNum = start[0];

        for (int i = 1; i < start.length; i++) {
            if (curNum + maxScore > start[i] + d) {
                return false;
            }
            curNum = Math.max(curNum + maxScore, start[i]);
        }

        return true;
    }

    /**
     * 贪心
     * 每次跳跃都跳到比当前数字大的索引上面，最后一个位置不需要满足这个条件
     */
    public long findMaximumScore(List<Integer> nums) {
        long ans = 0;

        int i = 0;
        for (int j = 1; j < nums.size(); j++) {

            if (j == nums.size() - 1) {
                ans += (long) (j - i) * nums.get(i);
                continue;
            }
            if (nums.get(j) <= nums.get(i)) {
                continue;
            }

            ans += (long) (j - i) * nums.get(i);
            i = j;
        }

        return ans;
    }

}
